use std::ptr::NonNull;

type QueueValue = *mut ();

const QUEUE_NULL: QueueValue = std::ptr::null_mut();

struct QueueEntry {
    data: QueueValue,
    prev: Option<NonNull<QueueEntry>>,
    next: Option<NonNull<QueueEntry>>,
}

struct Queue {
    head: Option<NonNull<QueueEntry>>,
    tail: Option<NonNull<QueueEntry>>,
}

impl Queue {
    fn new() -> Option<NonNull<Queue>> {
        let queue = Box::new(Queue {
            head: None,
            tail: None,
        });
        NonNull::new(Box::into_raw(queue))
    }

    fn free(&mut self) {
        while !self.is_empty() {
            self.pop_head();
        }
    }

    fn push_head(&mut self, data: QueueValue) -> bool {
        let new_entry = Box::new(QueueEntry {
            data,
            prev: None,
            next: self.head,
        });
        let new_entry_ptr = NonNull::new(Box::into_raw(new_entry));
        match new_entry_ptr {
            Some(entry_ptr) => {
                if let Some(head) = self.head {
                    unsafe { head.as_mut() }.prev = Some(entry_ptr);
                } else {
                    self.tail = new_entry_ptr;
                }
                self.head = new_entry_ptr;
                true
            }
            None => false,
        }
    }

    fn pop_head(&mut self) -> QueueValue {
        match self.head {
            Some(head_ptr) => {
                let head = unsafe { Box::from_raw(head_ptr.as_ptr()) };
                self.head = head.next;
                if let Some(new_head) = self.head {
                    unsafe { new_head.as_mut() }.prev = None;
                } else {
                    self.tail = None;
                }
                head.data
            }
            None => QUEUE_NULL,
        }
    }

    fn peek_head(&self) -> QueueValue {
        match self.head {
            Some(head_ptr) => unsafe { head_ptr.as_ref() }.data,
            None => QUEUE_NULL,
        }
    }

    fn push_tail(&mut self, data: QueueValue) -> bool {
        let new_entry = Box::new(QueueEntry {
            data,
            prev: self.tail,
            next: None,
        });
        let new_entry_ptr = NonNull::new(Box::into_raw(new_entry));
        match new_entry_ptr {
            Some(entry_ptr) => {
                if let Some(tail) = self.tail {
                    unsafe { tail.as_mut() }.next = Some(entry_ptr);
                } else {
                    self.head = new_entry_ptr;
                }
                self.tail = new_entry_ptr;
                true
            }
            None => false,
        }
    }

    fn pop_tail(&mut self) -> QueueValue {
        match self.tail {
            Some(tail_ptr) => {
                let tail = unsafe { Box::from_raw(tail_ptr.as_ptr()) };
                self.tail = tail.prev;
                if let Some(new_tail) = self.tail {
                    unsafe { new_tail.as_mut() }.next = None;
                } else {
                    self.head = None;
                }
                tail.data
            }
            None => QUEUE_NULL,
        }
    }

    fn peek_tail(&self) -> QueueValue {
        match self.tail {
            Some(tail_ptr) => unsafe { tail_ptr.as_ref() }.data,
            None => QUEUE_NULL,
        }
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_queue_new_free() {
        let queue = Queue::new();
        assert!(queue.is_some());
        unsafe {
            let queue_ref = &mut *queue.unwrap().as_ptr();
            queue_ref.free();
        }
    }

    #[test]
    fn test_queue_push_head() {
        let mut queue = Queue::new().unwrap();
        unsafe {
            let queue_ref = &mut *queue.as_ptr();
            assert!(queue_ref.push_head(&1));
            assert!(queue_ref.push_head(&2));
            assert!(queue_ref.push_head(&3));
            assert!(queue_ref.push_head(&4));
            assert_eq!(
                queue_ref.peek_head() as *const i32 as usize,
                &4 as *const i32 as usize
            );
        }
    }

    #[test]
    fn test_queue_pop_head() {
        let mut queue = Queue::new().unwrap();
        unsafe {
            let queue_ref = &mut *queue.as_ptr();
            queue_ref.push_head(&1);
            queue_ref.push_head(&2);
            queue_ref.push_head(&3);
            queue_ref.push_head(&4);
            assert_eq!(
                queue_ref.pop_head() as *const i32 as usize,
                &4 as *const i32 as usize
            );
            assert_eq!(
                queue_ref.pop_head() as *const i32 as usize,
                &3 as *const i32 as usize
            );
            assert_eq!(
                queue_ref.pop_head() as *const i32 as usize,
                &2 as *const i32 as usize
            );
            assert_eq!(
                queue_ref.pop_head() as *const i32 as usize,
                &1 as *const i32 as usize
            );
        }
    }

    // Additional test cases would go here...
}
